package datastructure;

/**
 * @author XY
 * @version 1.0
 * @date 2022/2/9 10:47
 * @Description
 */
public class Leet67 {

    public static String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int i = a.length()-1,j=b.length()-1;
        int carry = 0;
        while(i>=0&&j>=0){
            //如果上一次计算需要进位，这次计算的时候要加上进位
            int sum = carry;
            //-'0' 是为了转换为正常数字，否则会转换为asc码
            sum+=a.charAt(i--)-'0';
            sum+=b.charAt(j--)-'0';
            //是否需要进位
            carry = sum/2;
            //相加后的值
            int res = sum%2;
            sb.append(res);
        }
        //计算剩余数字
        while(i>=0){
            int sum = carry;
            sum+=a.charAt(i--)-'0';
            carry = sum/2;
            int res = sum%2;
            sb.append(res);
        }
        while(j>=0){
            int sum = carry;
            sum+=b.charAt(j--)-'0';
            carry = sum/2;
            int res = sum%2;
            sb.append(res);
        }
        if(carry>0){
            sb.append(carry);
        }
        return sb.reverse().toString();
    }

    public static void main(String[] args) {

        System.out.println(addBinary("101","101"));
    }
}
